package recursive;

/**
 * x 的 n 次幂
 * https://leetcode-cn.com/problems/powx-n/
 * 计算 x 的 n 次幂，-100.0 < x < 100.0，-2^31 <= n <= 2^31-1，-104 <= x^n <= 104
 * 解题思路：x^n = x^(n/2) * x^(n/2)，每递归一次，n 缩小一半，时间复杂度由 O(n) 变为O(log n)
 * 注意：1、n < 0 时，x^n = 1/(x^(-n))，因此可以先计算 x^(-n)
 *      2、n 为奇数时，x^n = x^(n/2) * x^(n/2) * x
 *      3、n 转换为 -n 的时候，注意边界 -2147483648 需要执行 n * -1L 进项强制类型转换才能运算成功
 * 测试案例：1、（8.84372，-5）
 *         2、（2，5）
 *         3、（2，-2）
 *         4、（1，-2147483648）
 *         5、（2，-2147483648）
 */
public class Powxn {
    public double myPow(double x, int n) {
        if (n < 0) {
            return 1 / positiveCalc(x, n * -1L); // 转成正数执行计算，最终结果执行-1次幂
        }
        else
            return positiveCalc(x, n);
    }

    // 更改
    private double positiveCalc(double x, long n){
        if (n == 0)
            return 1;
        double temp = positiveCalc(x, n/2);
        double ans = temp * temp;
        if (n % 2 == 1) // 奇数次幂时，要多乘一次x
            ans = ans * x;
        return ans;
    }
}
